N = 1000;
T = [18,89,874,841,711,208,953,196,525,707,493,912,567,977,236,97,68,510,394,900,780,150,244,47,994,191,703,17,261,896,990,842,395,928,105,152,490,905,533,686,175,970,931,73,42,849,796,387,940,286,701,877,512,626,263,618,855,511,878,382,154,240,586,308,482,840,664,865,501,272,801,251,491,604,285,559,838,63,603,90,243,775,406,4,414,720,194,676,817,310,131,575,1000,460,808,431,642,872,19,881,768,875,635,145,325,449,684,885,173,423,468,229,250,190,646,182,942,622,949,133,899,188,376,589,861,943,903,813,170,645,599,910,624,554,532,785,908,669,383,304,365,498,463,139,329,320,974,571,689,2,447,341,403,907,782,693,277,683,972,12,658,799,792,985,392,193,967,653,9,777,316,69,83,798,508,371,420,32,199,175,388,98,822,836,587,267,969,944,476,805,38,535,30,339,585,973,77,883,918,558,823,774,16,821,971,453,859,961,951,416,288,540,333,29,947,748,278,156,108,124,893,166,614,397,809,140,607,921,51,113,443,433,311,722,524,857,385,355,481,354,829,20,742,943,740,138,375,344,828,712,23,989,471,939,598,413,965,839,867,886,235,441,546,5,451,820,788,714,564,640,469,724,64,271,964,811,521,720,324,914,472,497,435,708,734,674,634,690,729,794,136,317,565,757,843,237,121,650,233,198,332,543,76,632,286,880,562,92,613,552,794,847,843,72,932,753,516,209,186,291,486,359,72,769,228,926,54,70,755,405,882,157,275,526,766,253,522,122,569,404,891,114,49,648,300,25,137,844,673,373,815,856,696,737,220,505,52,911,330,907,744,103,981,895,641,602,515,573,743,151,289,591,761,738,96,588,159,719,7,633,479,901,537,986,39,322,35,594,538,262,293,44,762,65,806,791,212,340,3,816,192,162,34,254,238,296,232,352,111,705,123,186,321,129,759,825,169,264,802,519,572,579,581,309,294,473,134,391,795,906,223,925,630,100,327,67,852,621,109,401,697,657,608,797,938,299,566,201,221,706,274,517,24,390,751,306,786,185,258,74,225,57,104,536,358,731,913,503,456,824,386,33,726,298,204,570,371,252,367,59,660,172,561,594,943,450,807,682,636,269,437,923,528,95,462,854,936,530,50,844,369,22,800,927,694,396,946,415,765,605,695,409,735,781,148,549,350,710,380,970,919,363,592,361,348,678,427,202,393,700,495,736,14,479,454,886,814,930,227,112,898,627,421,713,93,889,557,102,465,975,749,259,364,187,672,610,576,776,545,756,84,146,654,783,419,265,580,603,370,979,892,688,125,372,163,929,399,623,312,40,171,425,37,504,176,945,747,116,941,336,962,709,583,81,506,203,249,925,307,638,467,563,457,514,377,430,183,241,565,728,728,448,601,31,459,487,284,379,883,958,667,426,741,1,368,91,488,864,338,58,720,837,446,658,168,978,494,628,239,730,550,127,18,283,548,144,216,770,353,866,644,281,119,956,221,662,862,745,128,625,717,470,282,218,868,153,668,255,582,618,268,331,915,466,246,505,546,666,266,879,848,434,458,816,405,966,587,113,779,357,53,99,617,280,858,934,181,649,606,833,793,725,595,613,890,346,107,577,21,790,147,335,10,71,444,504,15,970,281,480,214,739,760,143,349,787,211,539,995,656,897,612,222,398,247,957,863,544,343,11,142,178,36,273,764,24,492,733,476,315,483,659,830,459,948,784,8,647,637,461,80,94,445,721,314,916,160,997,541,980,465,955,231,523,527,121,812,141,48,602,531,683,374,910,513,789,234,215,362,950,615,210,954,671,53,984,195,999,428,716,75,381,264,555,681,976,87,318,826,860,46,101,245,651,117,763,26,219,74,88,303,850,620,518,407,560,876,639,452,679,276,41,347,987,651,165,61,256,963,410,489,337,778,411,911,326,998,248,675,670,601,496,85,593,992,732,302,590,846,873,149,698,184,702,115,198,328,6,715,574,216,197,224,167,629,110,578,200,509,417,301,853,920,622,803,315,199,556,319,464,665,616,226,62,27,78,810,408,596,342,13,933,106,496,968,402,946,773,222,663,217,692,832,499,680,292,831,213,279,542,478,704,295,519,818,55,727,270,983,60,155,937,177,529,378,993,752,429,827,532,207,257,120,661,760,206,749,556,439,547,242,991,436,834,384,43,621,179,397,842,164,600,767,82,475,933,205,952,422,870,474,440,553,645,424,45,982,28,597,334,66,699,935,118,455,389,568,208,917,287,442,815,772,174,555,10,894,869,502,758];